class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
        import heapq
        from collections import defaultdict
        if endWord not in wordList: return 0
        # 建立一个邻居哈希表 要求O(n)
        wordList.append(beginWord)
        neibor_map = defaultdict(set)
        for w in wordList:
            for i in range(len(w)):
                qword = w[:i] + '*'+w[i+1:]
                neibor_map[qword].add(w)
        # 使用启发式搜索 使用当前字母与结束字母的差值作为预估代价
        visited = set()
        short_distance = [(1+Diff(beginWord,endWord),1,beginWord)]
        heapq.heapify(short_distance)
        while short_distance:
            g_value,dis,node = heapq.heappop(short_distance)
            for i in range(len(node)):
                qword = node[:i] + '*'+node[i+1:]
                for neibor in neibor_map[qword]:
                    if neibor not in visited:
                        if neibor == endWord:
                            return dis + 1
                        visited.add(neibor)
                        heapq.heappush(short_distance,(dis+1+Diff(neibor,endWord),dis+1,neibor))
        
        return 0 



def Diff(s,t):
    result = 0
    for i in range(len(s)):
        if s[i] != t[i]:
            result += 1
    return result

s = Solution()
result = s.ladderLength(beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"])
print(result)